
@BOOK{KS2011:Expander,
  title = {Expander Families and Cayley Graphs},
  publisher = {Oxford University Press},
  year = {2011},
  author = {Mike Krebs and Anthony Shaheen},
  isbn = {978-0-19-976711-3},
  keywords = {expander},
  owner = {peterrobinson},
  timestamp = {2011.12.19}
}

@ARTICLE{G1998:Chernoff,
  author = {Gillman, David},
 title = {A Chernoff Bound for Random Walks on Expander Graphs},
 journal = {SIAM J. Comput.},
 issue_date = {Aug. 1998},
 volume = {27},
 number = {4},
 month = aug,
 year = {1998},
 issn = {0097-5397},
 pages = {1203--1220},
 numpages = {18},
 url = {http://dx.doi.org/10.1137/S0097539794268765},
 doi = {10.1137/S0097539794268765},
 acmid = {284979},
 publisher = {Society for Industrial and Applied Mathematics},
 address = {Philadelphia, PA, USA},
 keywords = {Ising system, Markov source, approximate counting, eigenvalue, entropy, expander, graph, large deviations, matching, partition function, random walk},
} 

@BOOK{MU2005:Probability,
  title = {Probability and computing - randomized algorithms and probabilistic
	analysis},
  publisher = {Cambridge University Press},
  year = {2005},
  author = {Michael Mitzenmacher and Eli Upfal},
  bibsource = {DBLP, http://dblp.uni-trier.de},
  isbn = {978-0-521-83540-4},
  keywords = {textbook}
}

@BOOK{L1994:Discrete,
  title = {Discrete groups, expanding graphs and invariant
measures, volume 125 of Progress in Mathematics},
  publisher = {Birkhäuser},
  year = {1994},
  author = {Alexander Lubotzky},
  bibsource = {DBLP, http://dblp.uni-trier.de},
  keywords = {textbook}
}

@book{S1998:Universal,
  author    = {Christian Scheideler},
  title     = {Universal Routing Strategies for Interconnection Networks},
  publisher = {Springer},
  series    = {Lecture Notes in Computer Science},
  volume    = {1390},
  year      = {1998},
  isbn      = {3-540-64505-5},
  ee        = {http://dx.doi.org/10.1007/BFb0052928},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@BOOK{AA2009:Number,
  title = {Number Theory: Structures, Examples, and Problems},
  publisher = {Birkh\"auser Boston},
  year = {2009},
  author = {Titu Andreescu and Dorin Andrica},
  edition = {first},
  keywords = {textbook, numbertheory}
}

@BOOK{MR1995:Randomized,
  title = {Randomized Algorithms},
  publisher = {Cambridge University Press},
  year = {1995},
  author = {Rajeev Motwani and Prabhakar Raghavan},
  bibsource = {DBLP, http://dblp.uni-trier.de},
  isbn = {0-521-47465-5}
}

@INPROCEEDINGS{APRU2012:Towards,
  author = {Augustine, John and Pandurangan, Gopal and Robinson, Peter and Upfal,
	Eli},
  title = {Towards Robust and Efficient Computation in Dynamic Peer-to-Peer
	Networks},
  booktitle = {SODA},
  year = {2012},
  groups = {private},
  interhash = {a86492a9c0977e23dbc23bb84b88effe},
  intrahash = {0a5065f448ef45870fffb1b67baa9c62},
  keywords = {myown},
  owner = {peterrobinson},
  timestamp = {2011-12-15 09:01:44},
  username = {monoid}
}


@book{AW04,
  author = {Hagit Attiya and Jennifer Welch},
  title = {Distributed Computing: Fundamentals, Simulations and Advanced Topics (2nd edition)},
  publisher = {John Wiley Interscience},
  year = {2004},
  month = {March},
  isbn = {0-471-453242}
}

@article{DemboZ98,
title={Large Deviations Techniques and Applications},
  author={Dembo, A. and Zeitouni, O.},
  isbn={9780387984063},
  lccn={97045236},
  series={Applications of mathematics},
  url={http://books.google.com/books?id=WmjDlhhDokIC},
  year={1998},
  publisher={Springer}
}


@book{grinstead1997introduction,
  title={Introduction to probability},
  author={Grinstead, C.M. and Snell, J.L.},
  isbn={9780821807491},
  lccn={97008126},
  url={http://books.google.com/books?id=14oq4uWGCkwC},
  year={1997},
  publisher={American Mathematical Society}
}


@inproceedings{KhanKMPT08,
 author = {Khan, Maleq and Kuhn, Fabian and Malkhi, Dahlia and Pandurangan, Gopal and Talwar, Kunal},
 title = {Efficient distributed approximation algorithms via probabilistic tree embeddings},
 booktitle = {Proceedings of the twenty-seventh ACM symposium on Principles of distributed computing},
 series = {PODC '08},
 year = {2008},
 isbn = {978-1-59593-989-0},
 location = {Toronto, Canada},
 pages = {263--272},
 numpages = {10},
 url = {http://doi.acm.org/10.1145/1400751.1400787},
 doi = {http://doi.acm.org/10.1145/1400751.1400787},
 acmid = {1400787},
 publisher = {ACM},
 address = {New York, NY, USA},
 keywords = {distributed approximation, generalized steiner forests, least element lists, metric spaces, network optimization, probabilistic tree embeddings},
} 

@article{AoyamaS08,
  author    = {Damon Mosk-Aoyama and
               Devavrat Shah},
  title     = {Fast Distributed Algorithms for Computing Separable Functions},
  journal   = {IEEE Transactions on Information Theory},
  volume    = {54},
  number    = {7},
  year      = {2008},
  pages     = {2997-3007},
  ee        = {http://dx.doi.org/10.1109/TIT.2008.924648},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@Book{ Pel00,
  author = "David Peleg",
  title = "Distributed Computing: A Locality-Sensitive Approach",
  publisher = "SIAM Society for Industrial and Applied Mathematics Monographs on Discrete Mathematics ans Applications",
  address = "Philadelphia",
  year = "2000",
  isbn = "0-89871-464-8" 
}

@ARTICLE{FLP85,
  author =	 "Michael J. Fischer and Nancy A. Lynch and
                  M. S. Paterson",
  title =	 "Impossibility of Distributed Consensus with one
                  Faulty Process",
  journal =	 "Journal of the ACM",
  volume =	 32,
  number =	 2,
  year =	 1985,
  month =	 apr,
  pages =	 "374--382",
}

@Article{AT98,
  author    = {Marcos Kawazoe Aguilera and
               Sam Toueg},
  title     = {A Simple Bivalency Proof that t-Resilient Consensus
               Requires t+1 Rounds},
  journal   = {Inf. Process. Lett.},
  volume    = {71},
  number    = {3--4},
  year      = {1999},
  pages     = {155--158},
  ee        = {http://dx.doi.org/10.1016/S0020-0190(99)00100-3},
}

@inproceedings{KSSV06,
  author    = {Valerie King and
               Jared Saia and
               Vishal Sanwalani and
               Erik Vee},
  title     = {Towards Secure and Scalable Computation in Peer-to-Peer
               Networks},
  booktitle = {FOCS},
  year      = {2006},
  pages     = {87-98}
}

@inproceedings{KOM11,
 author = {Kuhn, Fabian and Oshman, Rotem and Moses, Yoram},
 title = {Coordinated consensus in dynamic networks},
 booktitle = {Proceedings of the 30th annual ACM SIGACT-SIGOPS symposium on Principles of distributed computing},
 series = {PODC '11},
 year = {2011},
 isbn = {978-1-4503-0719-2},
 location = {San Jose, California, USA},
 pages = {1--10},
 numpages = {10},
 acmid = {1993808},
 publisher = {ACM},
} 

@article{Upfal94,
  author    = {Eli Upfal},
  title     = {Tolerating a Linear Number of Faults in Networks of Bounded
               Degree},
  journal   = {Inf. Comput.},
  volume    = {115},
  number    = {2},
  year      = {1994},
  pages     = {312-320},
  ee        = {http://dx.doi.org/10.1006/inco.1994.1099},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
@article{DPPU88,
  author    = {Cynthia Dwork and
               David Peleg and
               Nicholas Pippenger and
               Eli Upfal},
  title     = {Fault Tolerance in Networks of Bounded Degree},
  journal   = {SIAM J. Comput.},
  volume    = {17},
  number    = {5},
  year      = {1988},
  pages     = {975-988},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@inproceedings{CH:PODC10,
 author = {Censor Hillel, Keren and Shachnai, Hadas},
 title = {Partial information spreading with application to distributed maximum coverage},
 booktitle = {Proceeding of the 29th ACM SIGACT-SIGOPS symposium on Principles of distributed computing},
 series = {PODC '10},
 year = {2010},
 isbn = {978-1-60558-888-9},
 location = {Zurich, Switzerland},
 pages = {161--170},
 numpages = {10},
 url = {http://doi.acm.org.ezlibproxy1.ntu.edu.sg/10.1145/1835698.1835739},
 doi = {http://doi.acm.org.ezlibproxy1.ntu.edu.sg/10.1145/1835698.1835739},
 acmid = {1835739},
 publisher = {ACM},
} 

@inproceedings{ARS07,
 author = {Aspnes, James and Rustagi, Navin and Saia, Jared},
 title = {Worm Versus Alert: Who Wins in a Battle for Control of a Large-scale Network?},
 booktitle = {Proceedings of the 11th International Conference on Principles of Distributed Systems},
 series = {OPODIS'07},
 year = {2007},
 isbn = {3-540-77095-X, 978-3-540-77095-4},
 location = {Guadeloupe, French West Indies},
 pages = {443--456},
 numpages = {14},
 url = {http://dl.acm.org/citation.cfm?id=1782394.1782426},
 acmid = {1782426},
 publisher = {Springer-Verlag},
 address = {Berlin, Heidelberg},
 keywords = {epidemic processes, expander graphs, overlay network, peer-to-peer, self-certifying alert, worm},
} 

@article{BBCES2006,
  author    = {Amitabha Bagchi and
               Ankur Bhargava and
               Amitabh Chaudhary and
               David Eppstein and
               Christian Scheideler},
  title     = {The Effect of Faults on Network Expansion},
  journal   = {Theory Comput. Syst.},
  volume    = {39},
  number    = {6},
  year      = {2006},
  pages     = {903-928},
  ee        = {http://dx.doi.org/10.1007/s00224-006-1349-0},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@article{Cohen97,
  author    = {Edith Cohen},
  title     = {Size-Estimation Framework with Applications to Transitive
               Closure and Reachability},
  journal   = {J. Comput. Syst. Sci.},
  volume    = {55},
  number    = {3},
  year      = {1997},
  pages     = {441-453},
  ee        = {http://dx.doi.org/10.1006/jcss.1997.1534},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@article{MAS08,
  author    = {Damon Mosk-Aoyama and
               Devavrat Shah},
  title     = {Fast Distributed Algorithms for Computing Separable Functions},
  journal   = {IEEE Transactions on Information Theory},
  volume    = {54},
  number    = {7},
  year      = {2008},
  pages     = {2997-3007},
  ee        = {http://dx.doi.org/10.1109/TIT.2008.924648},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@INPROCEEDINGS{LS03,
author = {Gkantsidis, Christos and Mihail, Milena and Saberi, Amin},
 title = {Random Walks in Peer-to-peer Networks: Algorithms and Evaluation},
 journal = {Perform. Eval.},
 issue_date = {March 2006},
 volume = {63},
 number = {3},
 month = mar,
 year = {2006},
 issn = {0166-5316},
 pages = {241--263},
 numpages = {23},
 url = {http://dx.doi.org/10.1016/j.peva.2005.01.002},
 doi = {10.1016/j.peva.2005.01.002},
 acmid = {1141199},
 publisher = {Elsevier Science Publishers B. V.},
 address = {Amsterdam, The Netherlands, The Netherlands},
 keywords = {graph theory, peer-to-peer networks, random walks, statistics},
} 



@inproceedings{DGMSS11,
  author = {Doerr, Benjamin and Goldberg, Leslie Ann and Minder, Lorenz and Sauerwald, Thomas and Scheideler, Christian},
 title = {Stabilizing Consensus with the Power of Two Choices},
 booktitle = {Proceedings of the Twenty-third Annual ACM Symposium on Parallelism in Algorithms and Architectures},
 series = {SPAA '11},
 year = {2011},
 isbn = {978-1-4503-0743-7},
 location = {San Jose, California, USA},
 pages = {149--158},
 numpages = {10},
 url = {http://doi.acm.org/10.1145/1989493.1989516},
 doi = {10.1145/1989493.1989516},
 acmid = {1989516},
 publisher = {ACM},
 address = {New York, NY, USA},
 keywords = {distributed consensus, randomized algorithms, self-stabilization},
} 



@article{KS10,
 author = {King, Valerie and Saia, Jared},
 title = {Breaking the O(N2) Bit Barrier: Scalable Byzantine Agreement with an Adaptive Adversary},
 journal = {J. ACM},
 issue_date = {July 2011},
 volume = {58},
 number = {4},
 month = jul,
 year = {2011},
 issn = {0004-5411},
 pages = {18:1--18:24},
 articleno = {18},
 numpages = {24},
 url = {http://doi.acm.org/10.1145/1989727.1989732},
 doi = {10.1145/1989727.1989732},
 acmid = {1989732},
 publisher = {ACM},
 address = {New York, NY, USA},
 keywords = {Byzantine agreement, Monte Carlo Algorithms, Peer-to-peer, Samplers, consensus, distributed computing, secret-sharing},
} 




@inproceedings{KSS06,
 author = {King, Valerie and Saia, Jared and Sanwalani, Vishal and Vee, Erik},
 title = {Scalable Leader Election},
 booktitle = {Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithm},
 series = {SODA '06},
 year = {2006},
 isbn = {0-89871-605-5},
 location = {Miami, Florida},
 pages = {990--999},
 numpages = {10},
 url = {http://dl.acm.org/citation.cfm?id=1109557.1109667},
 acmid = {1109667},
 publisher = {Society for Industrial and Applied Mathematics},
 address = {Philadelphia, PA, USA},
} 

@article{KKKSS10,
  author = {Kapron, Bruce M. and Kempe, David and King, Valerie and Saia, Jared and Sanwalani, Vishal},
 title = {Fast Asynchronous Byzantine Agreement and Leader Election with Full Information},
 journal = {ACM Trans. Algorithms},
 issue_date = {August 2010},
 volume = {6},
 number = {4},
 month = sep,
 year = {2010},
 issn = {1549-6325},
 pages = {68:1--68:28},
 articleno = {68},
 numpages = {28},
 url = {http://doi.acm.org/10.1145/1824777.1824788},
 doi = {10.1145/1824777.1824788},
 acmid = {1824788},
 publisher = {ACM},
 address = {New York, NY, USA},
 keywords = {Byzantine agreement, Monte Carlo algorithms, asynchronous communication, distributed algorithms, probabilistic method},
} 

@Book{Lyn96,
  author =	 {Nancy Lynch},
  title =	 {Distributed Algorithms},
  publisher =	 {Morgan Kaufman Publishers, Inc.},
  address =      {San Francisco, USA},
  year =	 {1996},
}

@article{Dolev82,
 author = {Dolev, Danny},
 title = {The Byzantine Generals Strike Again},
 year = {1981},
 source = {http://www.ncstrl.org:8900/ncstrl/servlet/search?formname=detail\&id=oai%3Ancstrlh%3Astan%3ASTAN%2F%2FCS-TR-81-846},
 publisher = {Stanford University},
 address = {Stanford, CA, USA},
} 

@article{PSL80,
 author = {Pease, M. and Shostak, R. and Lamport, L.},
 title = {Reaching Agreement in the Presence of Faults},
 journal = {J. ACM},
 issue_date = {April 1980},
 volume = {27},
 number = {2},
 month = apr,
 year = {1980},
 issn = {0004-5411},
 pages = {228--234},
 numpages = {7},
 url = {http://doi.acm.org/10.1145/322186.322188},
 doi = {10.1145/322186.322188},
 acmid = {322188},
 publisher = {ACM},
 address = {New York, NY, USA},
} 



@misc{Cloudmark,
  author  = {Cloudmark Inc., Website of},
  title = {http://cloudmark.com/}
}

@article{SGG02,
  author = {Gummadi, P. Krishna and Saroiu, Stefan and Gribble, Steven D.},
 title = {A Measurement Study of Napster and Gnutella As Examples of Peer-to-peer File Sharing Systems},
 journal = {SIGCOMM Comput. Commun. Rev.},
 issue_date = {January 2002},
 volume = {32},
 number = {1},
 month = jan,
 year = {2002},
 issn = {0146-4833},
 pages = {82--82},
 numpages = {1},
 url = {http://doi.acm.org/10.1145/510726.510756},
 doi = {10.1145/510726.510756},
 acmid = {510756},
 publisher = {ACM},
 address = {New York, NY, USA},
} 


@inproceedings{SW02,
 author = {Sen, Subhabrata and Wang, Jia},
 title = {Analyzing peer-to-peer traffic across large networks},
 booktitle = {Proceedings of the 2nd ACM SIGCOMM Workshop on Internet measurment},
 series = {IMW '02},
 year = {2002},
 isbn = {1-58113-603-X},
 location = {Marseille, France},
 pages = {137--150},
 numpages = {14},
 publisher = {ACM},
 address = {New York, NY, USA},
} 

@inproceedings{SR06,
 author = {Stutzbach, Daniel and Rejaie, Reza},
 title = {Understanding churn in peer-to-peer networks},
 booktitle = {Proceedings of the 6th ACM SIGCOMM conference on Internet measurement},
 series = {IMC '06},
 year = {2006},
 isbn = {1-59593-561-4},
 location = {Rio de Janeriro, Brazil},
 pages = {189--202},
 numpages = {14},
 publisher = {ACM},
 address = {New York, NY, USA},
} 

@article{BG93,
 author = {Berman, Piotr and Garay, Juan A.},
 title = {Fast Consensus in Networks of Bounded Degree (Extended Abstract)},
 booktitle = {Proceedings of the 4th International Workshop on Distributed Algorithms},
 year = {1991},
 isbn = {0-387-54099-7},
 location = {Bari, Italy},
 pages = {321--333},
 numpages = {13},
 url = {http://dl.acm.org/citation.cfm?id=112007.112029},
 acmid = {112029},
 publisher = {Springer-Verlag New York, Inc.},
 address = {New York, NY, USA},
} 

@inproceedings{Canny02,
 author = {Canny, John},
 title = {Collaborative Filtering with Privacy via Factor Analysis},
 booktitle = {Proceedings of the 25th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval},
 series = {SIGIR '02},
 year = {2002},
 isbn = {1-58113-561-0},
 location = {Tampere, Finland},
 pages = {238--245},
 numpages = {8},
 url = {http://doi.acm.org/10.1145/564376.564419},
 doi = {10.1145/564376.564419},
 acmid = {564419},
 publisher = {ACM},
 address = {New York, NY, USA},
 keywords = {CSCW, collaborative filtering, missing data, personalization, privacy, recommender systems, sparse, surveys},
} 


@article{DBGWK06,
 author = {Datta, Souptik and Bhaduri, Kanishka and Giannella, Chris and Wolff, Ran and Kargupta, Hillol},
 title = {Distributed Data Mining in Peer-to-Peer Networks},
 journal = {IEEE Internet Computing},
 issue_date = {July 2006},
 volume = {10},
 number = {4},
 month = jul,
 year = {2006},
 issn = {1089-7801},
 pages = {18--26},
 numpages = {9},
 url = {http://dx.doi.org/10.1109/MIC.2006.74},
 doi = {10.1109/MIC.2006.74},
 acmid = {1159023},
 publisher = {IEEE Educational Activities Department},
 address = {Piscataway, NJ, USA},
 keywords = {P2P, data analysis, data mining, data mining, distributed computing, peer-to-peer systems, P2P, data analysis, distributed computing, peer-to-peer systems},
} 

@article{VAS04,
 author = {Vlachos, Vasileios and Androutsellis-Theotokis, Stephanos and Spinellis, Diomidis},
 title = {Security applications of peer-to-peer networks},
 journal = {Comput. Netw.},
 volume = {45},
 issue = {2},
 month = {June},
 year = {2004},
 issn = {1389-1286},
 pages = {195--205},
 numpages = {11},
 publisher = {Elsevier North-Holland, Inc.},
 address = {New York, NY, USA},
} 

@inproceedings{MS05,
  author = {Malan, David J. and Smith, Michael D.},
 title = {Host-based Detection of Worms Through Peer-to-peer Cooperation},
 booktitle = {Proceedings of the 2005 ACM Workshop on Rapid Malcode},
 series = {WORM '05},
 year = {2005},
 isbn = {1-59593-229-1},
 location = {Fairfax, VA, USA},
 pages = {72--80},
 numpages = {9},
 url = {http://doi.acm.org/10.1145/1103626.1103641},
 doi = {10.1145/1103626.1103641},
 acmid = {1103641},
 publisher = {ACM},
 address = {New York, NY, USA},
 keywords = {P2P, Win32, native API, peer-to-peer, system calls, system services, temporal consistency, windows, worms},
} 

@inproceedings{PRU01,
 author = {Pandurangan, G.},
 title = {Building Low-Diameter P2P Networks},
 booktitle = {Proceedings of the 42Nd IEEE Symposium on Foundations of Computer Science},
 series = {FOCS '01},
 year = {2001},
 isbn = {0-7695-1390-5},
 pages = {492--},
 url = {http://dl.acm.org/citation.cfm?id=874063.875584},
 acmid = {875584},
 publisher = {IEEE Computer Society},
 address = {Washington, DC, USA},
} 



@article {AS09,
 author = {Awerbuch, Baruch and Scheideler, Christian},
 title = {Towards a Scalable and Robust DHT},
 journal = {Theor. Comp. Sys.},
 issue_date = {June 2009},
 volume = {45},
 number = {2},
 month = jun,
 year = {2009},
 issn = {1432-4350},
 pages = {234--260},
 numpages = {27},
 url = {http://dx.doi.org/10.1007/s00224-008-9099-9},
 doi = {10.1007/s00224-008-9099-9},
 acmid = {1555959},
 publisher = {Springer-Verlag New York, Inc.},
 address = {Secaucus, NJ, USA},
} 



@inproceedings{FS02,
 author = {Fiat, Amos and Saia, Jared},
 title = {Censorship Resistant Peer-to-peer Content Addressable Networks},
 booktitle = {Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms},
 series = {SODA '02},
 year = {2002},
 isbn = {0-89871-513-X},
 location = {San Francisco, California},
 pages = {94--103},
 numpages = {10},
 url = {http://dl.acm.org/citation.cfm?id=545381.545392},
 acmid = {545392},
 publisher = {Society for Industrial and Applied Mathematics},
 address = {Philadelphia, PA, USA},
} 


@inproceedings{NW03,
  author = {Naor, Moni and Wieder, Udi},
  biburl = {http://www.bibsonomy.org/bibtex/2979f17232310caaac83df18200233f89/dblp},
  booktitle = {IPTPS},
  crossref = {conf/iptps/2003},
  editor = {Kaashoek, M. Frans and Stoica, Ion},
  ee = {http://dx.doi.org/10.1007/978-3-540-45172-3_8},
  interhash = {36b2b4edffb6b7fc8cbef8cb24049e89},
  intrahash = {979f17232310caaac83df18200233f89},
  isbn = {3-540-40724-3},
  keywords = {dblp},
  pages = {88-97},
  publisher = {Springer},
  series = {Lecture Notes in Computer Science},
  timestamp = {2011-07-05T00:00:00.000+0200},
  title = {A Simple Fault Tolerant Distributed Hash Table.},
  url = {http://dblp.uni-trier.de/db/conf/iptps/iptps2003.html#NaorW03},
  volume = 2735,
  year = 2003
}

@incollection{HK03,
    year={2003},
    isbn={978-3-540-20184-7},
    booktitle={Distributed Computing},
    volume={2848},
    series={Lecture Notes in Computer Science},
    editor={Fich, FaithEllen},
    doi={10.1007/978-3-540-39989-6_23},
    title={Asymptotically Efficient Approaches to Fault-Tolerance in Peer-to-Peer Networks},
    url={http://dx.doi.org/10.1007/978-3-540-39989-6_23},
    publisher={Springer Berlin Heidelberg},
    author={Hildrum, Kirsten and Kubiatowicz, John},
    pages={321-336},
    language={English}
}

@inproceedings{Scheideler05,
  author = {Scheideler, Christian},
 title = {How to Spread Adversarial Nodes?: Rotate!},
 booktitle = {Proceedings of the Thirty-seventh Annual ACM Symposium on Theory of Computing},
 series = {STOC '05},
 year = {2005},
 isbn = {1-58113-960-8},
 location = {Baltimore, MD, USA},
 pages = {704--713},
 numpages = {10},
 url = {http://doi.acm.org/10.1145/1060590.1060694},
 doi = {10.1145/1060590.1060694},
 acmid = {1060694},
 publisher = {ACM},
 address = {New York, NY, USA},
 keywords = {join-leave attacks, proactive security, random mixing},
} 


@inproceedings{BCF09,
 author = {Baumann, Herv{\'e} and Crescenzi, Pierluigi and Fraigniaud, Pierre},
 title = {Parsimonious Flooding in Dynamic Graphs},
 booktitle = {Proceedings of the 28th ACM Symposium on Principles of Distributed Computing},
 series = {PODC '09},
 year = {2009},
 isbn = {978-1-60558-396-9},
 location = {Calgary, AB, Canada},
 pages = {260--269},
 numpages = {10},
 url = {http://doi.acm.org/10.1145/1582716.1582757},
 doi = {10.1145/1582716.1582757},
 acmid = {1582757},
 publisher = {ACM},
 address = {New York, NY, USA},
 keywords = {broadcasting, epidemic protocol, evolving graphs, gossip protocol},
} 

@ARTICLE{APRU11,
   author = {{Augustine}, J. and {Pandurangan}, G. and {Robinson}, P. and 
	{Upfal}, E.},
    title = "{Towards Robust and Efficient Computation in Dynamic Peer-to-Peer Networks}",
  journal = {ArXiv e-prints},
archivePrefix = "arXiv",
   eprint = {1108.0809},
 primaryClass = "cs.DS",
 keywords = {Computer Science - Data Structures and Algorithms, Computer Science - Distributed, Parallel, and Cluster Computing},
     year = 2011,
    month = aug,
   adsurl = {http://adsabs.harvard.edu/abs/2011arXiv1108.0809A},
  adsnote = {Provided by the SAO/NASA Astrophysics Data System}
}

@inproceedings{FPJKA07,
 author = {Falkner, Jarret and Piatek, Michael and John, John P. and Krishnamurthy, Arvind and Anderson, Thomas},
 title = {Profiling a Million User Dht},
 booktitle = {Proceedings of the 7th ACM SIGCOMM Conference on Internet Measurement},
 series = {IMC '07},
 year = {2007},
 isbn = {978-1-59593-908-1},
 location = {San Diego, California, USA},
 pages = {129--134},
 numpages = {6},
 url = {http://doi.acm.org/10.1145/1298306.1298325},
 doi = {10.1145/1298306.1298325},
 acmid = {1298325},
 publisher = {ACM},
 address = {New York, NY, USA},
} 


@inproceedings{GKLL09,
  author = {Geambasu, Roxana and Kohno, Tadayoshi and Levy, Amit A. and Levy, Henry M.},
  title = {Vanish: Increasing Data Privacy with Self-destructing Data},
  booktitle = {Proceedings of the 18th Conference on USENIX Security Symposium},
  series = {SSYM'09},
  year = {2009},
  location = {Montreal, Canada},
  pages = {299--316},
  numpages = {18},
  url = {http://dl.acm.org/citation.cfm?id=1855768.1855787},
  acmid = {1855787},
  publisher = {USENIX Association},
  address = {Berkeley, CA, USA},
} 

@article{AS09,
 author = {Awerbuch, Baruch and Scheideler, Christian},
 title = {Towards a Scalable and Robust DHT},
 journal = {Theor. Comp. Sys.},
 issue_date = {June 2009},
 volume = {45},
 number = {2},
 month = jun,
 year = {2009},
 issn = {1432-4350},
 pages = {234--260},
 numpages = {27},
 url = {http://dx.doi.org/10.1007/s00224-008-9099-9},
 doi = {10.1007/s00224-008-9099-9},
 acmid = {1555959},
 publisher = {Springer-Verlag New York, Inc.},
 address = {Secaucus, NJ, USA},
} 

@inproceedings{PT11,
 author = {Pandurangan, Gopal and Trehan, Amitabh},
 title = {Xheal: Localized Self-healing Using Expanders},
 booktitle = {Proceedings of the 30th Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing},
 series = {PODC '11},
 year = {2011},
 isbn = {978-1-4503-0719-2},
 location = {San Jose, California, USA},
 pages = {301--310},
 numpages = {10},
 url = {http://doi.acm.org/10.1145/1993806.1993865},
 doi = {10.1145/1993806.1993865},
 acmid = {1993865},
 publisher = {ACM},
 address = {New York, NY, USA},
 keywords = {distributed, expanders, expansion, local, randomized, reconfiguration, self-healing, spectral properties},
} 


@inproceedings{FSY05,
 author = {Fiat, Amos and Saia, Jared and Young, Maxwell},
 title = {Making Chord Robust to Byzantine Attacks},
 booktitle = {Proceedings of the 13th Annual European Conference on Algorithms},
 series = {ESA'05},
 year = {2005},
 isbn = {3-540-29118-0, 978-3-540-29118-3},
 location = {Palma de Mallorca, Spain},
 pages = {803--814},
 numpages = {12},
 url = {http://dx.doi.org/10.1007/11561071_71},
 doi = {10.1007/11561071_71},
 acmid = {2104709},
 publisher = {Springer-Verlag},
 address = {Berlin, Heidelberg},
} 



@inproceedings{Hae11,
 author = {Haeupler, Bernhard},
 title = {Analyzing Network Coding Gossip Made Easy},
 booktitle = {Proceedings of the Forty-third Annual ACM Symposium on Theory of Computing},
 series = {STOC '11},
 year = {2011},
 isbn = {978-1-4503-0691-1},
 location = {San Jose, California, USA},
 pages = {293--302},
 numpages = {10},
 url = {http://doi.acm.org/10.1145/1993636.1993676},
 doi = {10.1145/1993636.1993676},
 acmid = {1993676},
 publisher = {ACM},
 address = {New York, NY, USA},
 keywords = {dynamic networks, gossip, multicast, network coding},
} 

 
@inproceedings{OW05,
 author = {O'Dell, Regina and Wattenhofer, Rogert},
 title = {Information Dissemination in Highly Dynamic Graphs},
 booktitle = {Proceedings of the 2005 Joint Workshop on Foundations of Mobile Computing},
 series = {DIALM-POMC '05},
 year = {2005},
 isbn = {1-59593-092-2},
 location = {Cologne, Germany},
 pages = {104--110},
 numpages = {7},
 url = {http://doi.acm.org/10.1145/1080810.1080828},
 doi = {10.1145/1080810.1080828},
 acmid = {1080828},
 publisher = {ACM},
 address = {New York, NY, USA},
 keywords = {dynamic graphs, flooding, mobile network, routing},
} 

@article{KSW10,
 year={2010},
 issn={0178-2770},
 journal={Distributed Computing},
 volume={22},
 number={4},
 doi={10.1007/s00446-010-0099-z},
 title={Towards worst-case churn resistant peer-to-peer systems},
 url={http://dx.doi.org/10.1007/s00446-010-0099-z},
 publisher={Springer-Verlag},
 keywords={Churn; Dynamic networks; Fault-tolerance; Overlay network; Peer-to-peer},
 author={Kuhn, Fabian and Schmid, Stefan and Wattenhofer, Roger},
 pages={249-267},
 language={English}
}


@incollection {SS09,
   author = {Scheideler, Christian and Schmid, Stefan},
   affiliation = {Technische Universität München Institut für Informatik D-85748 Garching Germany},
   title = {A Distributed and Oblivious Heap},
   booktitle = {Automata, Languages and Programming},
   series = {Lecture Notes in Computer Science},
   publisher = {Springer Berlin / Heidelberg},
   keyword = {Computer Science},
   pages = {571-582},
   volume = {5556},
   year = {2009}
}


@inproceedings{CRW11,
 author = {Chung, Hyun Chul and Robinson, Peter and Welch, Jennifer L.},
 title = {Optimal regional consecutive leader election in mobile ad-hoc networks},
 booktitle = {Proceedings of the 7th ACM ACM SIGACT/SIGMOBILE International Workshop on Foundations of Mobile Computing},
 series = {FOMC '11},
 year = {2011},
 isbn = {978-1-4503-0779-6},
 location = {San Jose, California},
 pages = {52--61},
 numpages = {10},
  ee        = {http://dx.doi.org/10.1007/s00446-010-0099-z},
 doi = {http://doi.acm.org/10.1145/1998476.1998485},
 acmid = {1998485},
 publisher = {ACM},
} 


@inproceedings{avin1, 
 author = {Avin, Chen and Borokhovich, Michael and Censor-Hillel, Keren and Lotker, Zvi},
 title = {Order Optimal Information Spreading Using Algebraic Gossip},
 booktitle = {Proceedings of the 30th Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing},
 series = {PODC '11},
 year = {2011},
 isbn = {978-1-4503-0719-2},
 location = {San Jose, California, USA},
 pages = {363--372},
 numpages = {10},
 url = {http://doi.acm.org/10.1145/1993806.1993883},
 doi = {10.1145/1993806.1993883},
 acmid = {1993883},
 publisher = {ACM},
 address = {New York, NY, USA},
 keywords = {algebraic gossip, gossip, network coding, tight bounds},
} 



@inproceedings{avin2,
  author = {Borokhovich, Michael and Avin, Chen and Lotker, Zvi},
  booktitle = {ISIT},
  crossref = {conf/isit/2010},
  ee = {http://doi.ieeecomputersociety.org/10.1109/ISIT.2010.5513272},
  interhash = {824b04a9a01c4bb6c51cef9da386cf8e},
  intrahash = {c528e5714d8b271b597dd18c39d2b92c},
  keywords = {dblp},
  pages = {1758-1762},
  publisher = {IEEE},
  timestamp = {2012-02-28T00:00:00.000+0100},
  title = {Tight bounds for algebraic gossip on graphs.},
  url = {http://dblp.uni-trier.de/db/conf/isit/isit2010.html#BorokhovichAL10},
  year = 2010
}


  
@article{kuhn-survey,
 author = {Kuhn, Fabian and Oshman, Rotem},
 title = {Dynamic Networks: Models and Algorithms},
 journal = {SIGACT News},
 issue_date = {March 2011},
 volume = {42},
 number = {1},
 month = mar,
 year = {2011},
 issn = {0163-5700},
 pages = {82--96},
 numpages = {15},
 url = {http://doi.acm.org/10.1145/1959045.1959064},
 doi = {10.1145/1959045.1959064},
 acmid = {1959064},
 publisher = {ACM},
 address = {New York, NY, USA},
} 



@inproceedings{kuhn+lo:dynamic,
 author = {Kuhn, Fabian and Lynch, Nancy and Oshman, Rotem},
 title = {Distributed Computation in Dynamic Networks},
 booktitle = {Proceedings of the Forty-second ACM Symposium on Theory of Computing},
 series = {STOC '10},
 year = {2010},
 isbn = {978-1-4503-0050-6},
 location = {Cambridge, Massachusetts, USA},
 pages = {513--522},
 numpages = {10},
 url = {http://doi.acm.org/10.1145/1806689.1806760},
 doi = {10.1145/1806689.1806760},
 acmid = {1806760},
 publisher = {ACM},
 address = {New York, NY, USA},
 keywords = {distributed algorithms, dynamic networks},
} 

@article{chernoff,
 ajournal = "Ann. Math. Statist.",
 author = "Chernoff, Herman",
 doi = "10.1214/aoms/1177729330",
 journal = "The Annals of Mathematical Statistics",
 month = "12",
 number = "4",
 pages = "493--507",
 publisher = "The Institute of Mathematical Statistics",
 title = "A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of Observations",
 url = "http://dx.doi.org/10.1214/aoms/1177729330",
 volume = "23",
 year = "1952"
}


@article{hoeffding,
  author =       "Hoeffding, Wassily",
  title =        "Probability Inequalities for Sums of Bounded Random Variables",
  journal =      "Journal of the American Statistical Association",
  year =         "1963",
  volume =    "58",
  number =    "301",
  pages =     "13--30",
  month =     "March",
  url = "http://www.jstor.org/stable/2282952?",
  bib2html_rescat = "Bandits",
}

@article{angluin,
  author = {Angluin, Dana and Valiant, Leslie G.},
  title = {Fast Probabilistic Algorithms for Hamiltonian Circuits and Matchings},
  booktitle = {Proceedings of the Ninth Annual ACM Symposium on Theory of Computing},
  series = {STOC '77},
  year = {1977},
  location = {Boulder, Colorado, USA},
  pages = {30--41},
  numpages = {12},
  url = {http://doi.acm.org/10.1145/800105.803393},
  doi = {10.1145/800105.803393},
  acmid = {803393},
  publisher = {ACM},
  address = {New York, NY, USA},
} 


@article{jain+ms:steiner,
   author = {Jain, Kamal and Mahdian, Mohammad and Salavatipour, Mohammad R.},
 title = {Packing Steiner Trees},
 booktitle = {Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms},
 series = {SODA '03},
 year = {2003},
 isbn = {0-89871-538-5},
 location = {Baltimore, Maryland},
 pages = {266--274},
 numpages = {9},
 url = {http://dl.acm.org/citation.cfm?id=644108.644154},
 acmid = {644154},
 publisher = {Society for Industrial and Applied Mathematics},
 address = {Philadelphia, PA, USA},
} 

@article{cheriyan+s:steiner,
 author = {Cheriyan, Joseph and Salavatipour, Mohammad R.},
 title = {Hardness and Approximation Results for Packing Steiner Trees},
 journal = {Algorithmica},
 issue_date = {April 2006},
 volume = {45},
 number = {1},
 month = apr,
 year = {2006},
 issn = {0178-4617},
 pages = {21--43},
 numpages = {23},
 url = {http://dx.doi.org/10.1007/s00453-005-1188-4},
 doi = {10.1007/s00453-005-1188-4},
 acmid = {1325660},
 publisher = {Springer-Verlag New York, Inc.},
 address = {Secaucus, NJ, USA},
 keywords = {Approximation algorithms, Hardness of approximation, Packing problems, Steiner trees},
} 



@article{charikar+ccdgg:steiner,
 author = {Charikar, Moses and Chekuri, Chandra},
 title = {Approximation Algorithms for Directed Steiner Problems},
 journal = {J. Algorithms},
 issue_date = {Oct. 1999},
 volume = {33},
 number = {1},
 month = oct,
 year = {1999},
 issn = {0196-6774},
 pages = {73--91},
 numpages = {19},
 url = {http://dx.doi.org/10.1006/jagm.1999.1042},
 doi = {10.1006/jagm.1999.1042},
 acmid = {334361},
 publisher = {Academic Press, Inc.},
 address = {Duluth, MN, USA},
 keywords = {Steiner tree problem, approximation algorithm, directed graph},
} 



@article{lau:steiner,
 author = {Lau\&\#x2020;, Lap Chi},
 title = {An Approximate Max-Steiner-Tree-Packing Min-Steiner-Cut Theorem},
 journal = {Combinatorica},
 issue_date = {February 2007},
 volume = {27},
 number = {1},
 month = feb,
 year = {2007},
 issn = {0209-9683},
 pages = {71--90},
 numpages = {20},
 url = {http://dx.doi.org/10.1007/s00493-007-0044-3},
 doi = {10.1007/s00493-007-0044-3},
 acmid = {1229815},
 publisher = {Springer-Verlag New York, Inc.},
 address = {Secaucus, NJ, USA},
 keywords = {05C40, 05C70, 68R10, 68W25},
} 




@article{guruswami+krsy,
 author = {Guruswami, Venkatesan and Khanna, Sanjeev and Rajaraman, Rajmohan and Shepherd, Bruce and Yannakakis, Mihalis},
 title = {Near-optimal Hardness Results and Approximation Algorithms for Edge-disjoint Paths and Related Problems},
 booktitle = {Proceedings of the Thirty-first Annual ACM Symposium on Theory of Computing},
 series = {STOC '99},
 year = {1999},
 isbn = {1-58113-067-8},
 location = {Atlanta, Georgia, USA},
 pages = {19--28},
 numpages = {10},
 url = {http://doi.acm.org/10.1145/301250.301262},
 doi = {10.1145/301250.301262},
 acmid = {301262},
 publisher = {ACM},
 address = {New York, NY, USA},
} 


@inproceedings{haeupler:gossip,
 author = {Haeupler, Bernhard},
 title = {Analyzing network coding gossip made easy},
 booktitle = {ACM STOC},
 year = {2011},
 pages = {293--302},
} 

@inproceedings{haeupler+k:dynamic,
 author = {Haeupler, Bernhard and Karger, David},
 title = {Faster Information Dissemination in Dynamic Networks via Network Coding},
 booktitle = {Proceedings of the 30th Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing},
 series = {PODC '11},
 year = {2011},
 isbn = {978-1-4503-0719-2},
 location = {San Jose, California, USA},
 pages = {381--390},
 numpages = {10},
 url = {http://doi.acm.org/10.1145/1993806.1993885},
 doi = {10.1145/1993806.1993885},
 acmid = {1993885},
 publisher = {ACM},
 address = {New York, NY, USA},
 keywords = {dynamic networks, gossip, multicast, network coding},
} 

@article{gafni:dynamic,
 author = {Gafni, Eli and Afek, Yehuda},
 title = {End-to-end Communication in Unreliable Networks},
 booktitle = {Proceedings of the Seventh Annual ACM Symposium on Principles of Distributed Computing},
 series = {PODC '88},
 year = {1988},
 isbn = {0-89791-277-2},
 location = {Toronto, Ontario, Canada},
 pages = {131--148},
 numpages = {18},
 url = {http://doi.acm.org/10.1145/62546.62570},
 doi = {10.1145/62546.62570},
 acmid = {62570},
 publisher = {ACM},
 address = {New York, NY, USA},
} 

@INPROCEEDINGS{afek+gr:slide,
 author = {Afek, Yehuda and Gafni, Eli and Ros{\'e}n, Adi},
 title = {The Slide Mechanism with Applications in Dynamic Networks},
 booktitle = {Proceedings of the Eleventh Annual ACM Symposium on Principles of Distributed Computing},
 series = {PODC '92},
 year = {1992},
 isbn = {0-89791-495-3},
 location = {Vancouver, British Columbia, Canada},
 pages = {35--46},
 numpages = {12},
 url = {http://doi.acm.org/10.1145/135419.135430},
 doi = {10.1145/135419.135430},
 acmid = {135430},
 publisher = {ACM},
 address = {New York, NY, USA},
} 


@article{awerbuch:adversarial,
 author = {Berenbrink, P. and Brinkmann, A. and Scheideler, C.},
 title = {Simple Routing Strategies for Adversarial Systems},
 booktitle = {Proceedings of the 42Nd IEEE Symposium on Foundations of Computer Science},
 series = {FOCS '01},
 year = {2001},
 isbn = {0-7695-1390-5},
 pages = {158--},
 url = {http://dl.acm.org/citation.cfm?id=874063.875545},
 acmid = {875545},
 publisher = {IEEE Computer Society},
 address = {Washington, DC, USA},
} 

@article{awerbuch:icalp,
 author = {Awerbuch, Baruch and Brinkmann, Andr{\'e} and Scheideler, Christian},
 title = {Anycasting in Adversarial Systems: Routing and Admission Control},
 booktitle = {Proceedings of the 30th International Conference on Automata, Languages and Programming},
 series = {ICALP'03},
 year = {2003},
 isbn = {3-540-40493-7},
 location = {Eindhoven, The Netherlands},
 pages = {1153--1168},
 numpages = {16},
 url = {http://dl.acm.org/citation.cfm?id=1759210.1759320},
 acmid = {1759320},
 publisher = {Springer-Verlag},
 address = {Berlin, Heidelberg},
 keywords = {adversarial routing, anycasting, dynamic networks, load balancing, online algorithms},
} 

@book{leighton:book,
 author = {Leighton, F. Thomson},
 title = {Introduction to Parallel Algorithms and Architectures: Array, Trees, Hypercubes},
 year = {1992},
 isbn = {1-55860-117-1},
 publisher = {Morgan Kaufmann Publishers Inc.},
 address = {San Francisco, CA, USA},
} 



@article{topkis:disseminate,
 author = {Topkis, Donald M.},
 title = {Concurrent Broadcast for Information Dissemination},
 journal = {IEEE Trans. Softw. Eng.},
 issue_date = {October 1985},
 volume = {11},
 number = {10},
 month = oct,
 year = {1985},
 issn = {0098-5589},
 pages = {1107--1112},
 numpages = {6},
 url = {http://dx.doi.org/10.1109/TSE.1985.231858},
 doi = {10.1109/TSE.1985.231858},
 acmid = {4514},
 publisher = {IEEE Press},
 address = {Piscataway, NJ, USA},
} 



@book{dolev:stabilize,
 author = {Dolev, Shlomi},
 title = {Self-stabilization},
 year = {2000},
 isbn = {0-262-04178-2},
 publisher = {MIT Press},
 address = {Cambridge, MA, USA},
} 

@article{gafni+b:link-reversal,
author = {Gafni, Eli M. and Bertsekas, Dimitri P.},
  biburl = {http://www.bibsonomy.org/bibtex/2d43e9cc971bdcabcf5566869f2dde751/msteele},
  booktitle = {IEEE Transactions on Communications},
  file = {:I\:\\My Documents\\Thesis\\Research\\Gafni81.pdf:PDF},
  interhash = {d2417fcd207f8be5631c8dab20a8775a},
  intrahash = {d43e9cc971bdcabcf5566869f2dde751},
  keywords = {imported},
  month = jan,
  organization = {IEEE},
  owner = {msteele},
  pages = {11-18},
  publisher = {IEEE},
  series = {IEEE Transactions on Communications},
  timestamp = {2011-07-15T15:18:02.000+0200},
  title = {{Distributed Algorithms for Generating Loop-Free Routes in Networks
	with Frequently Changing Topology}},
  url = {http://www.mit.edu/people/dimitrib/Gafni_Loopfree.pdf},
  volume = 29,
  year = 1981
}


@INPROCEEDINGS{afek+ag:dynamic,                                                                            
 author = {Afek, Yehuda and Awerbuch, Baruch and Gafni, Eli},
 title = {Applying Static Network Protocols to Dynamic Networks},
 booktitle = {Proceedings of the 28th Annual Symposium on Foundations of Computer Science},
 series = {SFCS '87},
 year = {1987},
 isbn = {0-8186-0807-2},
 pages = {358--370},
 numpages = {13},
 url = {http://dx.doi.org/10.1109/SFCS.1987.7},
 doi = {10.1109/SFCS.1987.7},
 acmid = {1382993},
 publisher = {IEEE Computer Society},
 address = {Washington, DC, USA},
}      

@INPROCEEDINGS{awerbuch+pps:dynamic,
 author = {Awerbuch, Baruch and Patt-Shamir, Boaz and Peleg, David and Saks, Michael},
 title = {Adapting to Asynchronous Dynamic Networks (Extended Abstract)},
 booktitle = {Proceedings of the Twenty-fourth Annual ACM Symposium on Theory of Computing},
 series = {STOC '92},
 year = {1992},
 isbn = {0-89791-511-9},
 location = {Victoria, British Columbia, Canada},
 pages = {557--570},
 numpages = {14},
 url = {http://doi.acm.org/10.1145/129712.129767},
 doi = {10.1145/129712.129767},
 acmid = {129767},
 publisher = {ACM},
 address = {New York, NY, USA},
} 


@inproceedings{awerbuch+l:flow,
 author = {Awerbuch, Baruch and Leighton, Tom},
 title = {Improved Approximation Algorithms for the Multi-commodity Flow Problem and Local Competitive Routing in Dynamic Networks},
 booktitle = {Proceedings of the Twenty-sixth Annual ACM Symposium on Theory of Computing},
 series = {STOC '94},
 year = {1994},
 isbn = {0-89791-663-8},
 location = {Montreal, Quebec, Canada},
 pages = {487--496},
 numpages = {10},
 url = {http://doi.acm.org/10.1145/195058.195238},
 doi = {10.1145/195058.195238},
 acmid = {195238},
 publisher = {ACM},
 address = {New York, NY, USA},
} 

@inproceedings{awerbuch+bbs:route,
 author = {Berenbrink, P. and Brinkmann, A. and Scheideler, C.},
 title = {Simple Routing Strategies for Adversarial Systems},
 booktitle = {Proceedings of the 42Nd IEEE Symposium on Foundations of Computer Science},
 series = {FOCS '01},
 year = {2001},
 isbn = {0-7695-1390-5},
 pages = {158--},
 url = {http://dl.acm.org/citation.cfm?id=874063.875545},
 acmid = {875545},
 publisher = {IEEE Computer Society},
 address = {Washington, DC, USA},
} 

@inproceedings{jia+rs:adhoc,
 author = {Jia, Lujun and Rajaraman, Rajmohan and Scheideler, Christian},
 title = {On Local Algorithms for Topology Control and Routing in Ad Hoc Networks},
 booktitle = {Proceedings of the Fifteenth Annual ACM Symposium on Parallel Algorithms and Architectures},
 series = {SPAA '03},
 year = {2003},
 isbn = {1-58113-661-7},
 location = {San Diego, California, USA},
 pages = {220--229},
 numpages = {10},
 url = {http://doi.acm.org/10.1145/777412.777447},
 doi = {10.1145/777412.777447},
 acmid = {777447},
 publisher = {ACM},
 address = {New York, NY, USA},
 keywords = {ad hoc wireless networks, adversarial model, competitive analysis, distributed algorithms, mobile computing and communication, routing, spanners},
} 


@INPROCEEDINGS{awerbuch+bs:anycast,
 author = {Awerbuch, Baruch and Brinkmann, Andr{\'e} and Scheideler, Christian},
 title = {Anycasting in Adversarial Systems: Routing and Admission Control},
 booktitle = {Proceedings of the 30th International Conference on Automata, Languages and Programming},
 series = {ICALP'03},
 year = {2003},
 isbn = {3-540-40493-7},
 location = {Eindhoven, The Netherlands},
 pages = {1153--1168},
 numpages = {16},
 url = {http://dl.acm.org/citation.cfm?id=1759210.1759320},
 acmid = {1759320},
 publisher = {Springer-Verlag},
 address = {Berlin, Heidelberg},
 keywords = {adversarial routing, anycasting, dynamic networks, load balancing, online algorithms},
} 


@article{alon+blp:radio,
 author = {Alon, Noga and Bar-Noy, Amotz and Linial, Nathan and Peleg, David},
 title = {A Lower Bound for Radio Broadcast},
 journal = {J. Comput. Syst. Sci.},
 issue_date = {Oct. 1991},
 volume = {43},
 number = {2},
 month = oct,
 year = {1991},
 issn = {0022-0000},
 pages = {290--298},
 numpages = {9},
 url = {http://dx.doi.org/10.1016/0022-0000(91)90015-W},
 doi = {10.1016/0022-0000(91)90015-W},
 acmid = {114569},
 publisher = {Academic Press, Inc.},
 address = {Orlando, FL, USA},
} 


@INPROCEEDINGS{clementi+ms:radio,
 author = {Clementi, Andrea E. F. and Monti, Angelo and Silvestri, Riccardo},
 title = {Distributed Multi-broadcast in Unknown Radio Networks},
 booktitle = {Proceedings of the Twentieth Annual ACM Symposium on Principles of Distributed Computing},
 series = {PODC '01},
 year = {2001},
 isbn = {1-58113-383-9},
 location = {Newport, Rhode Island, USA},
 pages = {255--264},
 numpages = {10},
 url = {http://doi.acm.org/10.1145/383962.384040},
 doi = {10.1145/383962.384040},
 acmid = {384040},
 publisher = {ACM},
 address = {New York, NY, USA},
} 


@inproceedings{bar-yehuda+gi:radio,
 author = {Bar-Yehuda, Reuven and Goldreich, Oded and Itai, Alon},
 title = {On the Time-complexity of Broadcast in Radio Networks: An Exponential Gap Between Determinism Randomization},
 booktitle = {Proceedings of the Sixth Annual ACM Symposium on Principles of Distributed Computing},
 series = {PODC '87},
 year = {1987},
 isbn = {0-89791-239-X},
 location = {Vancouver, British Columbia, Canada},
 pages = {98--108},
 numpages = {11},
 url = {http://doi.acm.org/10.1145/41840.41849},
 doi = {10.1145/41840.41849},
 acmid = {41849},
 publisher = {ACM},
 address = {New York, NY, USA},
} 



@article{ahlswede+cly:coding,
 author = {Ahlswede, R. and Cai, Ning and Li, S. -Y.R. and Yeung, R. W.},
 title = {Network Information Flow},
 journal = {IEEE Trans. Inf. Theor.},
 issue_date = {July 2000},
 volume = {46},
 number = {4},
 month = sep,
 year = {2006},
 issn = {0018-9448},
 pages = {1204--1216},
 numpages = {13},
 url = {http://dx.doi.org/10.1109/18.850663},
 doi = {10.1109/18.850663},
 acmid = {2266188},
 publisher = {IEEE Press},
 address = {Piscataway, NJ, USA},
} 



@inproceedings{zosin+k:steiner,
 author = {Zosin, Leonid and Khuller, Samir},
 title = {On Directed Steiner Trees},
 booktitle = {Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms},
 series = {SODA '02},
 year = {2002},
 isbn = {0-89871-513-X},
 location = {San Francisco, California},
 pages = {59--63},
 numpages = {5},
 url = {http://dl.acm.org/citation.cfm?id=545381.545388},
 acmid = {545388},
 publisher = {Society for Industrial and Applied Mathematics},
 address = {Philadelphia, PA, USA},
} 

@INPROCEEDINGS{sanders+et:flow,
 author = {Sanders, Peter and Egner, Sebastian and Tolhuizen, Ludo},
 title = {Polynomial Time Algorithms for Network Information Flow},
 booktitle = {Proceedings of the Fifteenth Annual ACM Symposium on Parallel Algorithms and Architectures},
 series = {SPAA '03},
 year = {2003},
 isbn = {1-58113-661-7},
 location = {San Diego, California, USA},
 pages = {286--294},
 numpages = {9},
 url = {http://doi.acm.org/10.1145/777412.777464},
 doi = {10.1145/777412.777464},
 acmid = {777464},
 publisher = {ACM},
 address = {New York, NY, USA},
 keywords = {coding, communication, derandomization, finite field, linear algebra, multicasting, network information theory, randomized algorithm},
} 



@inproceedings{kempe1, 
 author = {Kempe, David and Kleinberg, Jon M.},
 title = {Protocols and Impossibility Results for Gossip-Based Communication Mechanisms},
 booktitle = {Proceedings of the 43rd Symposium on Foundations of Computer Science},
 series = {FOCS '02},
 year = {2002},
 isbn = {0-7695-1822-2},
 pages = {471--480},
 numpages = {10},
 url = {http://dl.acm.org/citation.cfm?id=645413.652161},
 acmid = {652161},
 publisher = {IEEE Computer Society},
 address = {Washington, DC, USA},
} 



@inproceedings{chen-spaa,
 author = {Chen, Jen-Yeu and Pandurangan, Gopal},
 title = {Optimal Gossip-based Aggregate Computation},
 booktitle = {Proceedings of the Twenty-second Annual ACM Symposium on Parallelism in Algorithms and Architectures},
 series = {SPAA '10},
 year = {2010},
 isbn = {978-1-4503-0079-7},
 location = {Thira, Santorini, Greece},
 pages = {124--133},
 numpages = {10},
 url = {http://doi.acm.org/10.1145/1810479.1810504},
 doi = {10.1145/1810479.1810504},
 acmid = {1810504},
 publisher = {ACM},
 address = {New York, NY, USA},
 keywords = {aggregate computation, distributed randomized protocols, gossip-based protocols, lower bounds, probabilistic analysis},
} 

@inproceedings{demers,
 author = {Demers, Alan and Greene, Dan and Hauser, Carl and Irish, Wes and Larson, John and Shenker, Scott and Sturgis, Howard and Swinehart, Dan and Terry, Doug},
 title = {Epidemic Algorithms for Replicated Database Maintenance},
 booktitle = {Proceedings of the Sixth Annual ACM Symposium on Principles of Distributed Computing},
 series = {PODC '87},
 year = {1987},
 isbn = {0-89791-239-X},
 location = {Vancouver, British Columbia, Canada},
 pages = {1--12},
 numpages = {12},
 url = {http://doi.acm.org/10.1145/41840.41841},
 doi = {10.1145/41840.41841},
 acmid = {41841},
 publisher = {ACM},
 address = {New York, NY, USA},
} 


@inproceedings{shah,
 author = {Mosk-Aoyama, Damon and Shah, Devavrat},
 title = {Computing Separable Functions via Gossip},
 booktitle = {Proceedings of the Twenty-fifth Annual ACM Symposium on Principles of Distributed Computing},
 series = {PODC '06},
 year = {2006},
 isbn = {1-59593-384-0},
 location = {Denver, Colorado, USA},
 pages = {113--122},
 numpages = {10},
 url = {http://doi.acm.org/10.1145/1146381.1146401},
 doi = {10.1145/1146381.1146401},
 acmid = {1146401},
 publisher = {ACM},
 address = {New York, NY, USA},
 keywords = {data aggregation, gossip, randomized algorithms},
} 


@inproceedings{karp,
 author = {Karp, R. and Schindelhauer, C. and Shenker, S. and Vocking, B.},
 title = {Randomized Rumor Spreading},
 booktitle = {Proceedings of the 41st Annual Symposium on Foundations of Computer Science},
 series = {FOCS '00},
 year = {2000},
 isbn = {0-7695-0850-2},
 pages = {565--},
 url = {http://dl.acm.org/citation.cfm?id=795666.796561},
 acmid = {796561},
 publisher = {IEEE Computer Society},
 address = {Washington, DC, USA},
 keywords = {address-oblivious algorithm, commmunication complexity, communication complexity, communication optimality, communication overhead, database theory, distributed database copies, epidemic algorithms, information theory, lazy update transmission, lower bound, message transmissions, parallel rounds, random telephone calls, randomised algorithms, randomized communication mechanism, randomized rumor spreading, randomly selected communication partner, replicated databases, robustness, time optimality},
} 

@inproceedings{kempe,
 author = {Kempe, David and Dobra, Alin and Gehrke, Johannes},
 title = {Gossip-Based Computation of Aggregate Information},
 booktitle = {Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science},
 series = {FOCS '03},
 year = {2003},
 isbn = {0-7695-2040-5},
 pages = {482--},
 url = {http://dl.acm.org/citation.cfm?id=946243.946317},
 acmid = {946317},
 publisher = {IEEE Computer Society},
 address = {Washington, DC, USA},
} 

@article{boyd,
author = {Boyd, S. and Ghosh, A. and Prabhakar, B. and Shah, D.},
 title = {Randomized Gossip Algorithms},
 journal = {IEEE Trans. Inf. Theor.},
 issue_date = {June 2006},
 volume = {52},
 number = {6},
 month = jun,
 year = {2006},
 issn = {0018-9448},
 pages = {2508--2530},
 numpages = {23},
 url = {http://dx.doi.org/10.1109/TIT.2006.874516},
 doi = {10.1109/TIT.2006.874516},
 acmid = {2272253},
 publisher = {IEEE Press},
 address = {Piscataway, NJ, USA},
 keywords = {Distributed averaging, gossip, random walk, scaling laws, semidefinite programming, sensor networks}
} 


@INPROCEEDINGS{berenbrink+ceg:gossip,
 author = {Berenbrink, Petra and Czyzowicz, Jurek and Els\"{a}sser, Robert and G\k{a}sieniec, Leszek},
 title = {Efficient Information Exchange in the Random Phone-call Model},
 booktitle = {Proceedings of the 37th International Colloquium Conference on Automata, Languages and Programming: Part II},
 series = {ICALP'10},
 year = {2010},
 isbn = {3-642-14161-7, 978-3-642-14161-4},
 location = {Bordeaux, France},
 pages = {127--138},
 numpages = {12},
 url = {http://dl.acm.org/citation.cfm?id=1880999.1881013},
 acmid = {1881013},
 publisher = {Springer-Verlag},
 address = {Berlin, Heidelberg},
} 


@ARTICLE{bar-noy+gns:multicast,
 author = {Bar-Noy, Amotz and Guha, Sudipto},
 title = {Message Multicasting in Heterogeneous Networks},
 journal = {SIAM J. Comput.},
 issue_date = {2000},
 volume = {30},
 number = {2},
 month = apr,
 year = {2000},
 issn = {0097-5397},
 pages = {347--358},
 numpages = {12},
 url = {http://dx.doi.org/10.1137/S0097539798347906},
 doi = {10.1137/S0097539798347906},
 acmid = {587001},
 publisher = {Society for Industrial and Applied Mathematics},
 address = {Philadelphia, PA, USA},
 keywords = {LogP model, approximation algorithms, combinatorial optimization, heterogeneous networks, multicast, postal model},
} 


@inproceedings{avin+kl:dynamic,
 author = {Avin, Chen and Kouck\'{y}, Michal and Lotker, Zvi},
 title = {How to Explore a Fast-Changing World (Cover Time of a Simple Random Walk on Evolving Graphs)},
 booktitle = {Proceedings of the 35th International Colloquium on Automata, Languages and Programming, Part I},
 series = {ICALP '08},
 year = {2008},
 isbn = {978-3-540-70574-1},
 location = {Reykjavik, Iceland},
 pages = {121--132},
 numpages = {12},
 url = {http://dx.doi.org/10.1007/978-3-540-70575-8_11},
 doi = {10.1007/978-3-540-70575-8_11},
 acmid = {1427910},
 publisher = {Springer-Verlag},
 address = {Berlin, Heidelberg},
} 


@inproceedings{agarwal+c:coding,
title = "On the advantage of Network Coding for Improving Network Throughput",
author = "Agarwal, A. and Charikar, M.",
booktitle = "Information Theory Workshop",
year = "2004",
}

@article{deb+mc:coding,
 author = {Deb, Supratim and M{\'e}dard, Muriel and Choute, Clifford},
 title = {Algebraic Gossip: A Network Coding Approach to Optimal Multiple Rumor Mongering},
 journal = {IEEE/ACM Trans. Netw.},
 issue_date = {June 2006},
 volume = {14},
 number = {SI},
 month = jun,
 year = {2006},
 issn = {1063-6692},
 pages = {2486--2507},
 numpages = {22},
 url = {http://dx.doi.org/10.1109/TIT.2006.874532},
 doi = {10.1109/TIT.2006.874532},
 acmid = {1148678},
 publisher = {IEEE Press},
 address = {Piscataway, NJ, USA},
 keywords = {gossip algorithms, message dissemination, network coding},
} 



@inproceedings{LBK02,
 author = {Liben-Nowell, David and Balakrishnan, Hari and Karger, David},
 title = {Analysis of the Evolution of Peer-to-peer Systems},
 booktitle = {Proceedings of the Twenty-first Annual Symposium on Principles of Distributed Computing},
 series = {PODC '02},
 year = {2002},
 isbn = {1-58113-485-1},
 location = {Monterey, California},
 pages = {233--242},
 numpages = {10},
 url = {http://doi.acm.org/10.1145/571825.571863},
 doi = {10.1145/571825.571863},
 acmid = {571863},
 publisher = {ACM},
 address = {New York, NY, USA},
} 



@inproceedings{MNR02,
 author = {Malkhi, Dahlia and Naor, Moni and Ratajczak, David},
 title = {Viceroy: A Scalable and Dynamic Emulation of the Butterfly},
 booktitle = {Proceedings of the Twenty-first Annual Symposium on Principles of Distributed Computing},
 series = {PODC '02},
 year = {2002},
 isbn = {1-58113-485-1},
 location = {Monterey, California},
 pages = {183--192},
 numpages = {10},
 url = {http://doi.acm.org/10.1145/571825.571857},
 doi = {10.1145/571825.571857},
 acmid = {571857},
 publisher = {ACM},
 address = {New York, NY, USA},
} 

@article{CDG07,
 author = {Cooper, Colin and Dyer, Martin and Greenhill, Catherine},
 title = {Sampling Regular Graphs and a Peer-to-Peer Network},
 journal = {Comb. Probab. Comput.},
 issue_date = {July 2007},
 volume = {16},
 number = {4},
 month = jul,
 year = {2007},
 issn = {0963-5483},
 pages = {557--593},
 numpages = {37},
 url = {http://dx.doi.org/10.1017/S0963548306007978},
 doi = {10.1017/S0963548306007978},
 acmid = {1273849},
 publisher = {Cambridge University Press},
 address = {New York, NY, USA},
} 



@inproceedings{Kuhn2005self-repairing,
 author = {Kuhn, Fabian and Schmid, Stefan and Wattenhofer, Roger},
 title = {A Self-repairing Peer-to-peer System Resilient to Dynamic Adversarial Churn},
 booktitle = {Proceedings of the 4th International Conference on Peer-to-Peer Systems},
 series = {IPTPS'05},
 year = {2005},
 isbn = {3-540-29068-0, 978-3-540-29068-1},
 location = {Ithaca, NY},
 pages = {13--23},
 numpages = {11},
 url = {http://dx.doi.org/10.1007/11558989_2},
 doi = {10.1007/11558989_2},
 acmid = {2138962},
 publisher = {Springer-Verlag},
 address = {Berlin, Heidelberg},
} 

@inproceedings{JP,
  author    = {Suresh Jagannathan and
               Gopal Pandurangan and
               Siriam Srinivasan},
  title     = {Query Protocols for Highly Resilient Peer-to-Peer Networks},
  booktitle = {ISCA PDCS},
  year      = {2006},
  pages     = {247-252},
  crossref  = {DBLP:conf/ISCApdcs/2006},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@book {MR0163361,
    	AUTHOR = {Harris, Theodore E.},
     	TITLE = {The theory of branching processes},
   	 SERIES = {Die Grundlehren der Mathematischen Wissenschaften, Bd. 119},
 	PUBLISHER = {Springer-Verlag},
  	 ADDRESS = {Berlin},
      	YEAR = {1963},
     	PAGES = {xiv+230},
   	MRCLASS = {60.67},
  	MRNUMBER = {0163361 (29 \#664)},
	MRREVIEWER = {P. A. P. Moran},
}


@article{Madras1992255,
title = "Branching random walks on trees",
journal = "Stochastic Processes and their Applications",
volume = "42",
number = "2",
pages = "255 - 267",
year = "1992",
note = "",
issn = "0304-4149",
doi = "10.1016/0304-4149(92)90038-R",
url = "http://www.sciencedirect.com/science/article/pii/030441499290038R",
author = "Neal Madras and Rinaldo Schinazi"
}

@article{benjamini2010trace,
  title={On the trace of branching random walks},
  author={Benjamini, Itai and M{\"u}ller, Sebastian},
  journal={arXiv preprint arXiv:1002.2781},
  year={2010}
}

@inproceedings{cooper2012coalescing,
 author = {Cooper, Colin and Els\"{a}sser, Robert and Ono, Hirotaka and Radzik, Tomasz},
 title = {Coalescing Random Walks and Voting on Graphs},
 booktitle = {Proceedings of the 2012 ACM Symposium on Principles of Distributed Computing},
 series = {PODC '12},
 year = {2012},
 isbn = {978-1-4503-1450-3},
 location = {Madeira, Portugal},
 pages = {47--56},
 numpages = {10},
 url = {http://doi.acm.org/10.1145/2332432.2332440},
 doi = {10.1145/2332432.2332440},
 acmid = {2332440},
 publisher = {ACM},
 address = {New York, NY, USA},
 keywords = {distributed voting, random walks},
} 



@article{arthreya2005branching,
 year={2005},
 issn={0178-8051},
 journal={Probability Theory and Related Fields},
 volume={131},
 number={3},
 doi={10.1007/s00440-004-0377-4},
 title={Branching-coalescing particle systems},
 url={http://dx.doi.org/10.1007/s00440-004-0377-4},
 publisher={Springer-Verlag},
 keywords={First Schlögl Model; Reaction-diffusion process; Autocatalytic reaction; Branching; Coalescence; Resampling; Selection; Mutation; Contact process},
 author={Arthreya, Siva R. and Swart, Jan M},
 pages={376-414},
 language={English}
}


@article{sun2008brownian,
  title={The Brownian net},
  author={Sun, Rongfeng and Swart, Jan M},
  journal={The Annals of Probability},
  volume={36},
  number={3},
  pages={1153--1208},
  year={2008},
  publisher={Institute of Mathematical Statistics}
}

@article{matthews1988covering,
ajournal = "Ann. Probab.",
author = "Matthews, Peter",
doi = "10.1214/aop/1176991894",
journal = "The Annals of Probability",
month = "01",
number = "1",
pages = "189--199",
publisher = "The Institute of Mathematical Statistics",
title = "Covering Problems for Brownian Motion on Spheres",
url = "http://dx.doi.org/10.1214/aop/1176991894",
volume = "16",
year = "1988"
}


@inproceedings{mihail1989conductance,
 author = {Mihail, M.},
 title = {Conductance and Convergence of Markov Chains-a Combinatorial Treatment of Expanders},
 booktitle = {Proceedings of the 30th Annual Symposium on Foundations of Computer Science},
 series = {SFCS '89},
 year = {1989},
 isbn = {0-8186-1982-1},
 pages = {526--531},
 numpages = {6},
 url = {http://dx.doi.org/10.1109/SFCS.1989.63529},
 doi = {10.1109/SFCS.1989.63529},
 acmid = {1398642},
 publisher = {IEEE Computer Society},
 address = {Washington, DC, USA},
 keywords = {general irreversible Markov chains, combinatorial argument, convergence rate, conductance, random walks, expanders, linear algebra, time-reversible Markov chains},
} 






